/**
 * str1是否包含str2
 * @param {string} str1
 * @param {string} str2
 * @return {number}
 */
function KMP (str1, str2) {
  if (!str1 || !str2 || !str2.length || str2.length > str1.length) {
    return -1
  }
  const chars1 = str1.match(/./g)
  const chars2 = str2.match(/./g)
  const next = getNextArray(chars2)
  let i1 = 0
  let i2 = 0
  while (i1 < str1.length && i2 < str2.length) {
    if (chars1[i1] === chars2[i2]) {
      i1++
      i2++
    } else if (i2 > 0) {
      i2 = next[i2]
    } else {
      i1++
    }
  }
  return i2 === str2.length ? i1 - i2 : -1
}

/**
 * 获取next数组: 记录每个位置最长前缀后缀匹配
 * @param {string[]} str
 * @return {number[]}
 */
function getNextArray (str) {
  if (str.length === 1) {
    return [-1]
  }
  const next = new Array(str.length)
  next[0] = -1
  next[1] = 0
  let cn = 0
  let i = 2
  while (i < next.length) {
    if (str[i - 1] === str[cn]) {
      next[i++] = ++cn
    } else if (cn > 0) {
      cn = next[cn]
    } else {
      next[i++] = 0
    }
  }
  return next
}

console.log(KMP('ababcababk', 'ca'))
